from typing import *
from math import log


class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        m = 17
        self.dp = [[-1] * m for _ in range(n)]
        for i, v in enumerate(parent):
            self.dp[i][0] = v
        for j in range(1, m):
            for i in range(1, n):
                if self.dp[i][j - 1] != -1:
                    self.dp[i][j] = self.dp[self.dp[i][j - 1]][j - 1]

    def f(self, k):
        a = int(log(k, 2))
        return a, k - pow(2, a)

    def getKthAncestor(self, node: int, k: int) -> int:
        if node == -1:
            return -1
        if k == 0:
            return node
        a, k = self.f(k)
        return self.getKthAncestor(self.dp[node][a], k)


tn = TreeAncestor(10, [-1, 0, 1, 2, 0, 1, 0, 4, 7, 1])
print(tn.getKthAncestor(6, 4))

from math import log2

a = 10224
print(log(a, 2))
print(log2(a))

b = 10223

m,n = 10,10
edges = [[]]


def getKthAncestor(self, node: int, k: int) -> int:
    for i in range(k.bit_length()):
        if (k >> i) & 1:  # k 的二进制从低到高第 i 位是 1
            node = self.pa[node][i]
            if node < 0: break
    return node

# 另一种写法，不断去掉 k 的最低位的 1
def getKthAncestor2(self, node: int, k: int) -> int:
    while k and node != -1:  # 也可以写成 ~node
        lb = k & -k
        node = self.pa[node][lb.bit_length() - 1]
        k ^= lb
    return node

